12.2 Networks (Graphs)
147
The maximum number of possible edges in a network isupper N left parenthesis upper N minus 1 right parenthesis divided by 2N(N −1)/2 (the factor
2 in the denominator arising because each edge has two endpoints); the connectivity
upper CC is the actual number of edges (which may be weighted by the strength of each
edge) divided by the maximum number. A graph withupper C equals 1C = 1 is known as complete.
The degree matrix upper DD is constructed as
upper D equals normal d normal i normal a normal g left parenthesis k 1 comma ellipsis comma k Subscript upper N Baseline right parenthesis commaD = diag(k1, . . . , kN) ,
(12.16)
wherek Subscript iki the degree of theiith node, from which the Laplace matrixupper L equals upper D minus upper AL = D −A and
the normalized Laplace matrix upper L overbar equals upper I minus upper D Superscript negative 1 Baseline upper A ¯L = I −D−1A can be determined. The eigenval-
ues of upper LL are useful for giving rapid information about the connectivity, robustness,
stability, and so forth.
Two important generic topologies of graphs are as follows:
(i) random (Erd˝os–Rényi) graphs. Each pair of nodes is connected with proba-
bility pp; the connectivity of such a network peaks strongly at its average value and
decays exponentially for large connectivities. The probabilityp left parenthesis k right parenthesisp(k) that a node haskk
edges is given bymu Superscript k Baseline e Superscript negative mu Baseline divided by k factorialμke−μ/k!, wheremu equals 2 upper N pμ = 2Np is the mean number of edges per node.
The smallest number of edges connecting a randomly chosen pair of nodes (i.e., the
network diameter upper LL) is tilde log upper N∼log N (cf. tilde upper N∼N for a regular network). The cliquishness
(clustering coefficient) German upper C equals muC = μ. This type of graph has a percolation-like transition.
If there are upper MM interconnexions, then when upper M equals upper N divided by 2M = N/2 a giant cluster of connected
nodes appears.
A special case of the random graph is the small world. This term applies to
networks in which the smallest number of edges connecting a randomly chosen pair
of nodes is comparable to thelog upper Nlog N expected for a random network (i.e., much smaller
than for a regular network), whereas the local properties are characteristic of a regular
network (i.e., the clustering coefficient is high). The name comes from the typical
response, “It’s a small world!” uttered when it turns out that two people meeting for
the first time and with no obvious connexion between them have a common friend. 12
(ii) the “scale-free” networks, in which the probability upper P left parenthesis k right parenthesisP(k) of a node having
kk links tilde k Superscript negative gamma∼k−γ, where gammaγ is some constant. 13 A characteristic feature of a scale-free
network is therefore that it possesses a very small number of highly connected nodes.
Many properties of the network are highly vulnerable to the removal of these nodes.
12 The first published account appears in F. Karinthy, Láncszemek (in: Címszavak a Nagy Encik-
lopédiához, vol. 1, pp. 349–354. Budapest: Szépirodalmi Könyvkiadó (1980). It was first published
in the 1920s). A simple way of constructing a model small-world network has been given by Watts
and Strogatz: Start with a ring of nodes each connected to theirkk nearest neighbours (i.e., a regular
network). Then detach connexions from one of their ends with probability pp and reconnect the
freed end to any other node (ifp equals 1p = 1, then we recover a random network). Aspp increases,upper LL falls
quite rapidly, butGerman upper CC only slowly (as3 left parenthesis mu minus 2 right parenthesis divided by left bracket 4 left parenthesis mu minus 1 right parenthesis right bracket3(μ −2)/[4(μ −1)]). The small-world property applies to the
régime with lowupper LL but highGerman upper CC.
13 Scale-free networks seem to be widespread in the world. The first systematic investigation of
their properties is supposed to have been conducted by Dominican monks in the thirteenth and
fourteenth centuries, in connexion with eradicating heresy.